import Foundation

public struct Array_Practice {
    
    // 合并两个有序数组
   public static func merge(_ nums1: inout [Int], _ nums2: [Int]) {
        var result = [Int]()
        var i = 0
        var j = 0
        while i < nums1.count && j < nums2.count {
            let a = nums1[i]
            let b = nums2[j]
            if a < b {
                result.append(a)
                i += 1
            } else {
                result.append(b)
                j += 1
            }
        }
        while i < nums1.count {
            result.append(nums1[i])
            i += 1
        }
        while j < nums2.count {
            result.append(nums2[j])
            j += 1
        }
        print("\(result)")
    }
    
    // MARK: - 把数组内的奇数排到前面
    public static func sortArray_oddToFront(arr: inout [Int]) -> [Int] {
        var index = 0
        // 将奇数移到数组的前面
        for i in 0..<arr.count {
            if arr[i] % 2 != 0 {
                arr.swapAt(index, i)
                index += 1
            }
        }
        return arr
    }
    
    // MARK: - 数字+1
    public static func plusOne(_ digits: [Int]) -> [Int] {
        var digits = digits
        var carry = 1
        for i in (0..<digits.count).reversed() {
            digits[i] += carry
            if digits[i] < 10 {
                carry = 0
                break
            } else {
                digits[i] = 0
                carry = 1
            }
        }
        if carry == 1 {
            digits.insert(1, at: 0)
        }
        return digits
    }
    
    // MARK: - 两个数组的交集
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var countDict = [Int: Int]()
        var result = [Int]()
        // 遍历, 记录数量
        for num in nums1 {
            countDict[num, default: 0] += 1
        }
        
        // 遍历, 查找交集
        for num in nums2 {
            if countDict[num] ?? 0 > 0 {
                // 加入元素
                result.append(num)
                countDict[num]! -= 1
            }
        }
        return result
    }
    
    // MARK: - 轮转数组
    func rotate(_ nums: inout [Int], _ k: Int) {
        for _ in (nums.count - k ..< nums.count).reversed() {
            if let num = nums.popLast() {
                nums.insert(num, at: 0)
            }
        }
    }
    
    public static func rotate2(_ nums: inout [Int], k: Int) -> [Int] {
        var left = 0
        var right = k
        while left < right {
            nums.swapAt(left, right)
            left += 1
            right -= 1
        }
        left = nums.count - k
        right = nums.count - 1
        
        while left < right {
            nums.swapAt(left, right)
            left += 1
            right -= 1
        }
        return nums.reversed()
    }
    
    public static func rotate3(_ nums: inout [Int], k: Int) -> [Int] {
        // 确保k不大于数组长度
        let k = k % nums.count
        
        // 反转整个数组 54321
        nums.reverse()
        print(nums)
        
        // 反转要旋转的部分 45321
        nums[..<k].reverse()
        print(nums)
        
        // 复原未旋转的部分 45123
        nums[k...].reverse()
        print(nums)
        
        return nums
    }
}
